package warm100;

import java.util.*;

public class topKFrequent_347 {
    public int[] topKFrequent(int[] nums, int k) {
        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++)
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        //优先队列
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> map.get(a) - map.get(b));
        //小根堆
        //这种写法导致无论次数多少都会加入堆中，再poll出来，冗余操作
//        for (int key : map.keySet()) {
//            pq.offer(key);
//            if (pq.size() > k)  //使小根堆里只有 k 个
//                pq.poll();
//        }
        //map的流式写法
        map.forEach((num, cnt) -> {
            if (pq.size() < k) {
                // 不足 k 个直接将当前数字加入到堆中
                pq.offer(num);
            } else if (map.get(pq.peek()) < cnt) {
                //堆顶的最小次数是否小于当前数字的出现次数
                // 若是，则删掉堆中出现次数最少的一个数字，将当前数字加入堆中。
                pq.poll();
                pq.offer(num);
            }
        });

        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = pq.poll();
        return res;
    }

    /**
     * 最快排序，1ms，100%
     * 并非实际意义的桶排序
     * 在数字很大的情况下相当大，如存在1000000时，桶的大小巨大无比
     * 时间复杂度与数组大小n 就无关
     * 使用一个桶存储所有可能出现的（ 频次 ）
     * 下标+min即为原始数值
     */
    public int[] topKFrequent2(int[] nums, int k) {
        int min = nums[0];
        int max = nums[0];
        // 获取数组的取值范围 [min,max]
        for (int num : nums) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        // 建立桶 ，size : max-min+1  使得任意一个num值都可以在桶中找到自己的位置
        int[] buckets = new int[max - min + 1];
        // 填充桶 桶中存的是值对应的频率
        for (int num : nums) {
            buckets[num - min]++;
        }
        int[] ans = new int[k];
        int index = 0, max_count = 0;
        // 在桶里找最大频率
        for (int val : buckets)
            if (val > max_count) max_count = val;
        // 从最大频率开始 频率循环递减 来逐个找出k个元素
        while (max_count > 0 && index < k) {
            // 遍历桶 找出频率为max_count的相对位置j  ，然后下标+min即为原始数值
            for (int j = 0; j < buckets.length; j++) {
                if (buckets[j] == max_count) {
                    ans[index++] = j + min;
                }
            }
            max_count--;
        }
        return ans;
    }

    /**
     * 自己尝试桶排序
     */
    public int[] topKFrequent3(int[] nums, int k) {
        int len = nums.length;
        //map统计数字和对应出现的频率
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++)
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        //最大频率，和最小频率
        int max_count = 0, min_count = map.get(nums[0]);
        for (int key : map.keySet()) {
            max_count = Math.max(max_count, map.get(key));
            min_count = Math.min(min_count , map.get(key));
        }
        //找到范围平方根
        int cnt = (int) Math.sqrt (max_count - min_count +1) ;
        //桶的尺寸
        int size = (max_count - min_count + 1) / cnt ;
        if( (max_count - min_count + 1) % cnt != 0) cnt ++; //防止落单的数字没有桶装
        //桶初始化，桶内存储数字
        List<Integer>[] list = new List[cnt];
        for (int  i = 0; i < cnt; i++)
            list[i] = new ArrayList();
        //扫描一遍数字和频率,加入桶内
        for (int key : map.keySet()) {
            int index = ( map.get(key) - min_count )/ size ;  //频率所在桶下标
            list[index].add(key);
        }
        //桶内升序排序
        for (List l : list)
            l.sort((a,b)->map.get(a)-map.get(b));
        int[] ans = new int[k];
        int index = 0;
        flag: for (int i=list.length-1; i>=0; i--) {
            for (int j = list[i].size()-1; j>=0; j--) {
                if (index == k) break flag;
                ans[index++] = list[i].get(j);
            }
        }
       return ans;
    }

}
